package BinaryTree;

import test0ne.TreeNode;

import java.util.Stack;

/**
 * 二叉树遍历， 主要看非递归方法
 */
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

//        preOrder1(root);
//        preOrder2(root);
        inOrder(root);
    }

    /**
     * 前序非递归1   https://blog.csdn.net/canmengmeng/article/details/81328352
     * 思路：  前序是根左右，  那么放入栈应该是  右、左、根
     * 既然先遍历根，那么先将根出栈，  然后放 右、 左
     * @param root
     */
    private static void preOrder1(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> s = new Stack<>();
        s.push(root);

        while (!s.isEmpty()) {
            TreeNode cur = s.pop();
            System.out.println(cur.val);
            if(cur.right!= null) {
                s.push(cur.right);
            }

            if(cur.left!= null) {
                s.push(cur.left);
            }
        }
    }

    /**
     * 前序遍历2
     * 先一直遍历最左一列， 如果到底后
     * 1. 弹出栈顶，拿到栈顶的右孩子节点，继续走循环
     * @param root
     */
    private static void preOrder2(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        StringBuilder stringBuilder = new StringBuilder();

        while (cur != null || !s.isEmpty()) {
            while (cur != null) {
                stringBuilder.append(cur.val).append(",");
                s.push(cur);
                cur = cur.left;
            }
            TreeNode p = s.pop();
            cur = p.right;
        }
        System.out.println(stringBuilder.toString().substring(0, stringBuilder.length()-1));
    }

    /**
     * 非递归 中序遍历
     * @param root
     */
    private static void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> s = new Stack<>();

        TreeNode cur = root;

        while (cur!=null || !s.isEmpty()) {
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            TreeNode p = s.pop();
            System.out.println(p.val);
            cur = p.right;
        }
    }

}
